/**
 * @ClassName : TspDynamicProgrammingIterative
 * @Author : 骆发茂
 * @Date: 2021/12/14 16:24
 * @Description :
 * 动态规划：
 * 旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，
 * 是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，
 * 路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。
 * 路径的选择目标是要求得的路径路程为所有路径之中的最小值。
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TspDynamicProgrammingIterative {

    private final int N, start;
    private final double[][] distance;
    private List<Integer> tour = new ArrayList<>();
    private double minTourCost = Double.POSITIVE_INFINITY;
    private boolean ranSolver = false;

    /** 如果只是传入矩阵，默认从0开始，distance是矩阵 */
    public TspDynamicProgrammingIterative(double[][] distance) {
        this(0, distance);
    }

    /** 传入start开始位置，distance是矩阵 */
    public TspDynamicProgrammingIterative(int start, double[][] distance) {
        N = distance.length;

        if (N <= 2) throw new IllegalStateException("N <= 2 not yet supported.");
        if (N != distance[0].length) throw new IllegalStateException("Matrix must be square (n x n)");
        if (start < 0 || start >= N) throw new IllegalArgumentException("Invalid start node.");
        if (N > 32)
            throw new IllegalArgumentException(
                    "Matrix too large! A matrix that size for the DP TSP problem with a time complexity of"
                            + "O(n^2*2^n) requires way too much computation for any modern home computer to handle");

        this.start = start;
        this.distance = distance;
    }

    // Returns the optimal tour for the traveling salesman problem.
    /*optimal最优的*/

    /** 返回最佳的路径 */
    public List<Integer> getTour() {
        if (!ranSolver) solve();
        return tour;
    }

    // Returns the minimal tour cost.

    /** 返回最佳的路径的消耗 */
    public double getTourCost() {
        if (!ranSolver) solve();
        return minTourCost;
    }

    // Solves the traveling salesman problem and caches solution.
    public void solve() {

        if (ranSolver) return;

        final int END_STATE = (1 << N) - 1;
        Double[][] memo = new Double[N][1 << N];

        // Add all outgoing edges from the starting node to memo table.
        for (int end = 0; end < N; end++) {
            if (end == start) continue;
            memo[end][(1 << start) | (1 << end)] = distance[start][end];
        }

        for (int r = 3; r <= N; r++) {
            for (int subset : combinations(r, N)) {
                if (notIn(start, subset)) continue;
                for (int next = 0; next < N; next++) {
                    if (next == start || notIn(next, subset)) continue;
                    int subsetWithoutNext = subset ^ (1 << next);
                    double minDist = Double.POSITIVE_INFINITY;
                    for (int end = 0; end < N; end++) {
                        if (end == start || end == next || notIn(end, subset)) continue;
                        double newDistance = memo[end][subsetWithoutNext] + distance[end][next];
                        if (newDistance < minDist) {
                            minDist = newDistance;
                        }
                    }
                    memo[next][subset] = minDist;
                }
            }
        }

        // Connect tour back to starting node and minimize cost.
        for (int i = 0; i < N; i++) {
            if (i == start) continue;
            double tourCost = memo[i][END_STATE] + distance[i][start];
            if (tourCost < minTourCost) {
                minTourCost = tourCost;
            }
        }

        int lastIndex = start;
        int state = END_STATE;
        tour.add(start);

        // Reconstruct TSP path from memo table.
        for (int i = 1; i < N; i++) {

            int bestIndex = -1;
            double bestDist = Double.POSITIVE_INFINITY;
            for (int j = 0; j < N; j++) {
                if (j == start || notIn(j, state)) continue;
                double newDist = memo[j][state] + distance[j][lastIndex];
                if (newDist < bestDist) {
                    bestIndex = j;
                    bestDist = newDist;
                }
            }

            tour.add(bestIndex);
            state = state ^ (1 << bestIndex);
            lastIndex = bestIndex;
        }

        tour.add(start);
        Collections.reverse(tour);

        ranSolver = true;
    }

    private static boolean notIn(int elem, int subset) {
        return ((1 << elem) & subset) == 0;
    }

    // This method generates all bit sets of size n where r bits
    // are set to one. The result is returned as a list of integer masks.

    /**
     * 此方法生成所有大小为 n 的位集，其中 r 位
     * 设置为1。结果作为整数掩码列表返回。
     */
    public static List<Integer> combinations(int r, int n) {
        List<Integer> subsets = new ArrayList<>();
        combinations(0, 0, r, n, subsets);
        return subsets;
    }

    // To find all the combinations of size r we need to recurse until we have
    // selected r elements (aka r = 0), otherwise if r != 0 then we still need to select
    // an element which is found after the position of our last selected element
    // 找到我们需要重复的大小r的所有组合，直到我们有
    ////选择R元素（AKA r = 0），否则如果r！= 0那么我们仍然需要选择
    ////在上次选定元素的位置之后找到的元素

    private static void combinations(int set, int at, int r, int n, List<Integer> subsets) {

        // Return early if there are more elements left to select than what is available.
        int elementsLeftToPick = n - at;
        if (elementsLeftToPick < r) return;

        // We selected 'r' elements so we found a valid subset!
        if (r == 0) {
            subsets.add(set);
        } else {
            for (int i = at; i < n; i++) {
                // Try including this element
                set ^= (1 << i);

                combinations(set, i + 1, r - 1, n, subsets);

                // Backtrack and try the instance where we did not include this element
                set ^= (1 << i);
            }
        }
    }

    public static void main(String[] args) {
        // Create adjacency matrix
        int n = 6;
        double[][] distanceMatrix = new double[n][n];
        for (double[] row : distanceMatrix) java.util.Arrays.fill(row, 10000);


        distanceMatrix[0][1] = 4;
        distanceMatrix[0][2] = 3;
        distanceMatrix[0][3] = 8;
        ////////          distanceMatrix[0][4] = ;
        distanceMatrix[0][5] = 5;

        distanceMatrix[1][0] = 4;
      //  distanceMatrix[1][1] = 31;
        distanceMatrix[1][2] = 7;
        ////////         distanceMatrix[1][3] = ;
        distanceMatrix[1][4] = 2;
        distanceMatrix[1][5] = 5;

        distanceMatrix[2][0] = 3;
        distanceMatrix[2][1] = 7;
  //      distanceMatrix[2][2] = 31;
        distanceMatrix[2][3] = 3;
        distanceMatrix[2][4] = 6;
        ////////         distanceMatrix[2][5] = ;

        distanceMatrix[3][0] = 8;
        ////////         distanceMatrix[3][1] = ;
        distanceMatrix[3][2] = 3;
        distanceMatrix[3][4] = 4;
   //     distanceMatrix[3][3] = 3;
        distanceMatrix[3][5] = 6;

        ////////       ////////     distanceMatrix[4][0] = ;
        distanceMatrix[4][1] = 2;
        distanceMatrix[4][2] = 6;
   ///     distanceMatrix[4][4] = 3;
        distanceMatrix[4][3] = 4;
        distanceMatrix[4][5] = 5;

        distanceMatrix[5][0] = 1;
        distanceMatrix[5][1] = 5;
        ////////// distanceMatrix[5][2] = ;
        distanceMatrix[5][3] = 6;
        distanceMatrix[5][4] = 5;

    //    distanceMatrix[5][5] = 3;



        int startNode = 0;
        TspDynamicProgrammingIterative solver =
                new TspDynamicProgrammingIterative(startNode, distanceMatrix);

        System.out.println("Tour: " + solver.getTour());

        System.out.println("Tour cost: " + solver.getTourCost());
    }
}